/*
 * @lc app=leetcode.cn id=147 lang=javascript
 *
 * [147] 对链表进行插入排序
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var insertionSortList = function(head) {
  if(!head || !head.next) return head;
  let ret = new ListNode(null, head);

  let pre = head, cur = head.next;
  while(cur) {
    let next = cur.next;
    // 如果cur > pre, 将两个指针向后移动一步
    if(cur.val >= pre.val) {
      cur = next;
      pre = pre.next;
      continue;
    };

    // 从当前出移除cur;
    pre.next = next;

    // 查找cur的合适位置，并插入。
    let p = ret;
    while(p.next && p.next.val < cur.val) {
      p = p.next;
    }
    cur.next = p.next;
    p.next = cur;

    cur = next;
  }

  return ret.next;
};
// @lc code=end

